/**
 * @Author ZhangCuirong
 * @Date 2025/9/23 11:20
 * @description:
 */
public class Solution134 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int[] diff = new int[gas.length];
        for (int i = 0; i < gas.length; i++) {
            diff[i] = gas[i] - cost[i];
        }
        int start = -1;
        int sum = 0;
        int minSum = Integer.MAX_VALUE;
        for (int i = 0; i < diff.length; i++) {
            sum += diff[i];
            if (sum < minSum) {
                minSum = sum;
                start = i + 1;
            }
        }
        if (sum >= 0) {
            return start == gas.length ? 0 : start;
        } else {
            return -1;
        }
    }

    public static void main(String[] args) {
        Solution134 solution = new Solution134();
        System.out.println(solution.canCompleteCircuit(new int[]{1, 2, 3, 4, 5}, new int[]{3, 4, 5, 1, 2}));
        System.out.println(solution.canCompleteCircuit(new int[]{2, 3, 4}, new int[]{3, 4, 3}));
        System.out.println(solution.canCompleteCircuit(new int[]{3, 1, 1}, new int[]{1, 2, 2}));
    }
}
